package 剑指offer_leetcode;

/**
 * JZ66构建乘积数组
 */
public class 剑指Offer66_构建乘积数组 {
    /**
     *  B[0]  = 1  A[1]  A[2]  A[3]    A[n-1]
     *  B[1]  = A[0]  1  A[2]  A[3]    A[n-1]
     *  B[2] = A[0]  A[1]  1  A[3]    A[n-1]
     *
     *  B[n-1] = A[0]  A[1]  A[2]    A[n-2]  1
     *
     *  分为上下
     *  下三角：    B[1] 在 B[0] 基础上 多个 A[0]   B[2] 在 B[1] 基础上多个 A[1]  从左到右累乘
     *  上三角：                       少个A[0]                     少个A[1]  从右到左累乘
     */
    public int[] constructArr(int[] a) {
        if(a.length==0)
            return a;
        //初始化数组B
        int[] B = new int[a.length];
        B[0] = 1;
        //先乘左边，从左到右
        for(int i = 1; i < a.length; i++)
            //每多一位由数组B左边的元素多乘一个前面a的元素
            B[i] = B[i - 1] * a[i - 1];
        int temp = 1;
        //再乘右边，从右到左
        for(int i = a.length - 1; i >= 0; i--){
            //temp为右边的累乘
            B[i] *= temp;
            temp *= a[i];
        }
        return  B;
    }
}
